package leetcode.code0084;

import java.util.ArrayList;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution84 implements IDebug {
	public static void main(String[] args) {
		Solution84 so = new Solution84();
		so.debug1();
		so.debug2();
		so.debug3();
	}

	public int largestRectangleArea(int[] heights) {
		int len = heights.length;
		Stack<ArrayList<Integer>> s = new Stack<>();
		int ans = 0;
		int leftInStack = -1;// 最左边界,受到数组中的0影响,一旦出现0,0左侧的矩形都废了,最小矩形结算的时候将被抛弃
		for (int i = 0; i < len; i++) {
			Integer r = null;// 矩形的右界坐标 , 在while结算栈顶时, 结算里面不同高度的矩形块时, 共用前面的底w,所以记录右界
			int w = 0;// 底边宽长度, r-l , l记录的是最左边的不可用的边界,所以w = r - l
			while (!s.isEmpty() && heights[s.peek().get(0)] > heights[i]) {
				// 结算栈顶系列, 能结算的矩形, 矮的矩形与长的矩形共底(因为当前被结算的矩形中,右侧的比当前的高,是可以组合到当前结算的矩形中的)
				ArrayList<Integer> list = s.pop();
				int h = heights[list.get(0)];// 结算举行的高度,在当前while中,这个高度会逐渐变小
				// 左边界
				// 当栈还有其他数据时,说明左边还有更小的矩形待结算,当前左边界就是这个最小边界的最右侧,l是左侧不可用边界,这样w=r-l就不用+1;(为了和左边界-1的时候统一)
				int l = s.isEmpty() ? leftInStack : s.peek().get(s.peek().size() - 1);// leftInStack 最后结算最小的矩形的时候,
																						// 左边界l可能是-1,一旦中间出现高度0的矩形,这个位置变成最左边界
				if (r == null)// 右边界是当前while中第一个出现的右边界,这里跟i没关系,i的矩形将等i等高的收集完,弹出时,会结算的.
					r = list.get(list.size() - 1);
				w = r - l;// 宽度,l是左侧不可用边界,这样w=r-l就不用+1;(为了和左边界-1的时候统一)
				int area = h * w;// 面积=高度*宽度
				ans = Math.max(ans, area);// 结算最大面积
				// 循环时,仍能结算的话,下一个栈顶的高度是小于当前轮次的高度的
				// 公用当前轮次底儿的一个矩形
			}
			if (!s.isEmpty() && heights[s.peek().get(0)] == heights[i]) {
				s.peek().add(i);
			} else if (heights[i] > 0) {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				s.add(list);
			} else if (heights[i] == 0) {
				leftInStack = i;// 更新最左边界,用于结算最后一个最矮的矩形,这个挫地炮的左边界l可不一定是-1
			}
		}
		Integer r = null;
		int w = 0;
		while (!s.isEmpty()) {
			// 结算栈顶系列 累加
			ArrayList<Integer> list = s.pop();
			int h = heights[list.get(0)];
			int l = s.isEmpty() ? leftInStack : s.peek().get(s.peek().size() - 1);
			if (r == null)
				r = list.get(list.size() - 1);
			w = r - l;
			int area = h * w;
			ans = Math.max(ans, area);
		}
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[2,1,5,6,2,3]";
		int e = 10;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[2,4]";
		int e = 4;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[4,2,0,3,2,5]";
		int e = 6;
		int r = this.largestRectangleArea(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

}
